package demo.niuke.demo3;

import org.apache.poi.ss.formula.functions.T;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

    public static void main(String[] args) {
        // [3,5,1,6,2,0,8,null,null,7,4]
        // p = 5, q = 1
        TreeNode root = new TreeNode(3);
        TreeNode left = new TreeNode(5);
        TreeNode right = new TreeNode(1);
        TreeNode leftLeft = new TreeNode(6);
        TreeNode leftRight = new TreeNode(2);
        TreeNode rightLeft = new TreeNode(0);
        TreeNode rightRight = new TreeNode(8);
        TreeNode leftLeftLeft = new TreeNode(7);
        TreeNode leftLeftRight = new TreeNode(4);
        root.left = left;
        root.right = right;
        left.left = leftLeft;
        left.right = leftRight;
        right.left = rightLeft;
        right.right = rightRight;
        leftLeft.left = leftLeftLeft;
        leftLeft.right = leftLeftRight;
        TreeNode ans = new Solution().lowestCommonAncestor(root, left, leftLeftRight);
        System.out.println(ans.val);
    }

    boolean flag = false;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        flag = false;
        List<TreeNode> pathP = new ArrayList<>();
        findPath(root, p, pathP);
        flag = false;
        List<TreeNode> pathQ = new ArrayList<>();
        findPath(root, q, pathQ);

        // 找到路径的公共节点
        for (int i = pathP.size() - 1; i >= 0; i--) {
            for (int j = pathQ.size() - 1; j >= 0; j--) {
                if (pathP.get(i) == pathQ.get(j)) {
                    return pathP.get(i);
                }
            }
        }
        return null;
    }


    public void findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null || flag) {
            return;
        }
        // 中序 左中右
        path.add(root);
        if (root.val == target.val) {
            flag = true;
            return;
        }
        findPath(root.left, target, path);
        findPath(root.right, target, path);
        // 恢复现场
        if (!flag) {
            path.remove(path.size() - 1);
        }
    }
}